package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150"/>只出现一次的数字 II(Single Number II)</a>
 * <p>给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。</p>
 * <p>你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [2,2,3,2]
 *      输出：3
 *
 * 示例 2：
 *      输入：nums = [0,1,0,1,0,1,99]
 *      输出：99
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *     <li>1 <= nums.length <= 3 * 10^4</li>
 *     <li>-2^31 <= nums[i] <= 2^31 - 1</li>
 *     <li>nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @see LC0136SingleNumber_S 只出现一次的数字(Single Number)
 * @since 2023/10/23 17:43
 */
public class LC0137SingleNumber_II_M {

    static class Solution {
        public int singleNumber(int[] nums) {
            int ret = 0;
            for (int i = 0; i < 32; i++) {
                // 记录当前位置上1，出现的次数
                int count = 0;
                for (int num : nums) {
                    count += (num >> i) & 1;
                }
                // 说明只出现一次的数，该位置的值为1
                if (count % 3 == 1) {
                    ret |= (1 << i);
                }
            }
            return ret;
        }
    }
}
